/********************************************************************************
* @Author: Zhenzhou Liu
* @Date: 2024-06-12
* @Description: 标准遍历解题代码
********************************************************************************/

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <uthash.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
}ListNode;

int Find(int *parent, int index) {
    if (parent[index] != index)
        parent[index] = Find(parent, parent[index]);
    return parent[index];
}

void Union(int *parent, int index1, int index2) {
    parent[Find(parent, index1)] = Find(parent, index2);
}

int findCircleNum(int **isConnected, int isConnectedSize, int *isConnectedColSize) {
    int parent[isConnectedSize];
    for (int i = 0; i < isConnectedSize; ++i) {
        parent[i] = i;
    }

    for (int i = 0; i < isConnectedSize; ++i) {
        for (int j = i + 1; j < isConnectedSize; ++j) {
            if (isConnected[i][j] == 1)
                Union(parent, i, j);
        }
    }

    int provinces = 0;
    for (int i = 0; i < isConnectedSize; ++i) {
        if (parent[i] == i)
            ++provinces;
    }
    return provinces;
}


int *eventualSafeNodes(int **graph, int graphSize, int *graphColSize, int *returnSize) {
    int *rg[graphSize];
    int rgCol[graphSize];
    memset(rgCol, 0, sizeof(rgCol));

    for (int i = 0; i < graphSize; ++i) {
        for (int j = 0; j < graphColSize[i]; ++j) {
            rgCol[graph[i][j]]++;
        }
    }

    for (int i = 0; i < graphSize; ++i) {
        rg[i] = (int *) malloc(sizeof(int) * rgCol[i]);
        rgCol[i] = 0;
    }

    for (int i = 0; i < graphSize; ++i) {
        for (int j = 0; j < graphColSize[i]; ++j) {
            rg[graph[i][j]][rgCol[graph[i][j]]++] = i;
        }
    }

    int inDeg[graphSize];
    memcpy(inDeg, graphColSize, sizeof(int) * graphSize);

    int que[10000];
    int left = 0, right = 0;
    for (int i = 0; i < graphSize; ++i) {
        if (inDeg[i] == 0)
            que[right++] = i;
    }

    while (left < right) {
        int y = que[left++];
        for (int i = 0; i < rgCol[y]; ++i) {
            if (--inDeg[rg[y][i]] == 0)
                que[right++] = rg[y][i];
        }
    }

    int *ans = malloc(sizeof(int) * graphSize);
    *returnSize = 0;
    for (int i = 0; i < graphSize; ++i) {
        if (inDeg[i] == 0)
            ans[(*returnSize)++] = i;
    }

    return ans;
}


bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
    int visited[roomsSize], queue[roomsSize];
    int left = 0, right = 1;
    int nums = 0;
    memset(visited, 0, sizeof(visited));

    queue[0] = 0;
    visited[0] = true;
    while (left < right) {
        int x = queue[left++];
        ++nums;

        for (int i = 0; i < roomsColSize[x]; ++i) {
            int y = rooms[x][i];
            if (!visited[y]) {
                visited[y] = true;
                queue[right++] = y;
            }
        }
    }

    return nums == roomsSize;
}

#define MIN(a, b) (a < b ? a : b)

struct ListNode *createListNode(int val) {
    struct ListNode *node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

void freeList(struct ListNode* list) {
    while (list) {
        struct ListNode* cur = list;
        list = list->next;
        free(cur);
    }
}

/**
 * todo leetcode调试
 * @param n
 * @param redEdges
 * @param redEdgesSize
 * @param redEdgesColSize
 * @param blueEdges
 * @param blueEdgesSize
 * @param blueEdgesColSize
 * @param returnSize
 * @return
 */
int* shortestAlternatingPaths(int n, int** redEdges, int redEdgesSize, int* redEdgesColSize, int** blueEdges, int blueEdgesSize, int* blueEdgesColSize, int* returnSize) {
    struct ListNode* next[2][n];
    for (int i = 0; i < n; ++i) {
        next[0][i] = NULL;
        next[1][i] = NULL;
    }

    for (int i = 0; i < redEdgesSize; ++i) {
        int startNode = redEdges[i][0], endNode = redEdges[i][1];
        struct ListNode* node = createListNode(endNode);
        node->next = next[0][startNode];
        next[0][startNode] = node;
    }

    for (int i = 0; i < blueEdgesSize; ++i) {
        int startNode = blueEdges[i][0], endNode = blueEdges[i][1];
        struct ListNode* node = createListNode(endNode);
        node->next = next[1][startNode];
        next[1][startNode] = node;
    }

    int dist[2][n];
    for (int i = 0; i < n; ++i) {
        dist[0][i] = INT_MAX;
        dist[1][i] = INT_MAX;
    }

    dist[0][0] = dist[1][0] = 0;
    int queue[2 * n][2];
    int head = 0, tail = 0;
    queue[tail][0] = 0, queue[tail++][1] = 0;
    queue[tail][0] = 1, queue[tail++][1] = 0;

    while (head < tail) {
        int color = queue[head][0], startNode = queue[head++][1];
        for (struct ListNode *node = next[1 - color][startNode]; node != NULL; node = node->next) {
            if (dist[1 - color][node->val] != INT_MAX)
                continue;
            dist[1 - color][node->val] = dist[color][startNode] + 1;
            queue[tail][0] = 1 - color;
            queue[tail++][1] = node->val;
        }
    }

    int* ans = (int*) calloc(n, sizeof(int));
    for (int i = 0; i < n; ++i) {
        ans[i] = MIN(dist[0][i], dist[1][0]);
        if (ans[i] == INT_MAX)
            ans[i] = -1;
    }

    for (int i = 0; i < n; ++i) {
        freeList(next[0][i]);
        freeList(next[1][i]);
    }
    *returnSize = n;
    return ans;
}

typedef struct {
    int key;
    struct ListNode *list;
    UT_hash_handle hh;
} HashListNode;

static int max(int a, int b) {
    return a > b ? a : b;
}

struct ListNode* listNodeCreate(int val) {
    struct ListNode* obj = (struct ListNode *) malloc(sizeof(struct ListNode));
    obj->val = val;
    obj->next = NULL;
    return obj;
}

void listFree(struct ListNode* head) {
    while (head) {
        struct ListNode* cur = head;
        head = head->next;
        free(cur);
    }
}

HashListNode *hashFindListNode(HashListNode **obj, int key) {
    HashListNode *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}


bool hashAddListNode(HashListNode **obj, int key, int val) {
    HashListNode *pEntry = hashFindListNode(obj, key);
    if (!pEntry) {
        pEntry = (HashListNode *) malloc(sizeof(HashListNode));
        pEntry->key = key;
        pEntry->list = listNodeCreate(val);
        HASH_ADD_INT(*obj, key, pEntry);
    } else {
        struct ListNode *cur = listNodeCreate(val);
        cur->next = pEntry->list;
        pEntry->list = cur;
    }
    return true;
}

struct ListNode *hashGetListNode(HashListNode **obj, int key) {
    HashListNode *pEntry = hashFindListNode(obj, key);
    if (pEntry) {
        return pEntry->list;
    } else {
        return NULL;
    }
}



void hashFreeListNode(HashListNode **obj) {
    HashListNode *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);
        listFree(curr->list);
        free(curr);
    }
}

int dfsListNode(int cur, const int *informTime, HashListNode **graph) {
    int res = 0;
    HashListNode *pEntry = hashFindListNode(graph, cur);
    if (pEntry) {
        for (struct ListNode *node = pEntry->list; node ; node = node->next) {
            int neighbor = node->val;
            res = max(res, dfsListNode(neighbor, informTime, graph));
        }
    }
    return res + informTime[cur];
}


int numOfMinutes(int n, int headID, int* manager, int managerSize, int* informTime, int informTimeSize) {
    HashListNode *graph = NULL;
    for (int i = 0; i < n; ++i) {
        hashAddListNode(&graph, manager[i], i);
    }
    return dfsListNode(headID, informTime, &graph);
}

typedef struct CityNode {
    int city;
    int direction;
    struct CityNode* next;
}CityNode;

CityNode *createCityNode(int city, int direction) {
    CityNode *obj = (CityNode *) malloc(sizeof(CityNode));
    obj->city = city;
    obj->direction = direction;
    obj->next = NULL;
    return obj;
}

void freeCityNode(CityNode *list) {
    while (list) {
        CityNode *temp = list;
        list = list->next;
        free(temp);
    }
}


int dfsCityNode(int cur, int parent, CityNode **graph) {
    int res = 0;
    for (CityNode *cityNode = graph[cur]; cityNode; cityNode = cityNode->next) {
        if (cityNode->city == parent)
            continue;

        res += cityNode->direction + dfsCityNode(cityNode->city, cur, graph);
    }
    return res;
}

int minReorder(int n, int** connections, int connectionsSize, int* connectionsColSize) {
    CityNode **graph = (CityNode **) calloc(n, sizeof(CityNode *));
    for (int i = 0; i < connectionsSize; ++i) {
        CityNode *edge1 = createCityNode(connections[i][1], 1);
        edge1->next = graph[connections[i][0]];
        graph[connections[i][0]] = edge1;
        CityNode *edge2 = createCityNode(connections[i][0], 0);
        edge2->next = graph[connections[i][1]];
        graph[connections[i][1]] = edge2;
    }

    int res = dfsCityNode(0, -1, graph);
    for (int i = 0; i < n; ++i) {
        freeCityNode(graph[i]);
    }
    free(graph);
    return res;
}


void dfsForPaths(int x, int **graph, int target, int *graphColSize, int **paths, int *returnSize, int **returnColumnSizes, int *stk, int stkSize) {
    if (x == target) {
        int *tmp = (int *) calloc(stkSize, sizeof(int));
        memcpy(tmp, stk, sizeof(int) * stkSize);
        paths[*returnSize] = tmp;
        (*returnColumnSizes)[(*returnSize)++] = stkSize;
        return;
    }

    for (int i = 0; i < graphColSize[x]; ++i) {
        stk[stkSize] = graph[x][i];
        dfsForPaths(stk[stkSize++], graph, target, graphColSize, paths, returnSize, returnColumnSizes, stk, stkSize);
        --stkSize;
    }
}

int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
    int** paths;
    int stk[15];
    int stkSize = 0;
    stk[stkSize++] = 0;
    paths = (int **) calloc(16384, sizeof(int *));
    *returnSize = 0;
    *returnColumnSizes = (int *) calloc(16384, sizeof(int));
    dfsForPaths(0, graph, graphSize - 1, graphColSize, paths, returnSize, returnColumnSizes, stk, stkSize);
    return paths;
}

typedef struct AdjNode {
    int val;
    struct AdjNode *next;
}AdjNode;

AdjNode *createAdjNode(int val) {
    AdjNode *node = (AdjNode *) malloc(sizeof(AdjNode));
    node->val = val;
    node->next = NULL;
    return node;
}

void freeAdjNode(AdjNode *list) {
    while (list) {
        AdjNode *tmp = list;
        list = list->next;
        free(tmp);
    }
}

void dfsForCriticalConnections(int cur, int parent, AdjNode **graph, int *returnSize, int **returnColumnSizes, int *low, int *time, int* idx,
                               int **ans) {
    low[cur] = time[cur] = ++(*idx);

    for (AdjNode* node = graph[cur]; node; node = node->next) {
        int child = node->val;
        if (time[child] == 0) {
            dfsForCriticalConnections(child, cur, graph, returnSize, returnColumnSizes, low, time, idx, ans);
            low[cur] = (low[cur] > low[child] ? low[child] : low[cur]);
            if (low[child] > time[cur]) {
                int *connection = (int *) calloc(2, sizeof(int));
                connection[0] = cur;
                connection[1] = child;
                ans[*returnSize] = connection;
                (*returnColumnSizes)[(*returnSize)++] = 2;
            }
        } else if (time[child] < time[cur] && child != parent)
            low[cur] = (low[cur] > time[child] ? time[child] : low[cur]);
    }
}


int** criticalConnections(int n, int** connections, int connectionsSize, int* connectionsColSize, int* returnSize, int** returnColumnSizes) {
    AdjNode **graph = (AdjNode **) calloc(n, sizeof(AdjNode *));
    for (int i = 0; i < connectionsSize; ++i) {
        int a = connections[i][0], b = connections[i][1];
        AdjNode *nodeA = createAdjNode(a);
        AdjNode *nodeB = createAdjNode(b);
        nodeB->next = graph[a];
        graph[a] = nodeB;
        nodeA->next = graph[b];
        graph[b] = nodeA;
    }

    *returnSize = 0;
    int **ans = (int **) calloc(1e5, sizeof(int *));
    *returnColumnSizes = (int *) calloc(1e5, sizeof(int));
    int low[n], time[n], idx = 0;
    memset(low, 0, sizeof(int) *n);
    memset(time, 0, sizeof(int) *n);
    dfsForCriticalConnections(0, -1, graph, returnSize, returnColumnSizes, low, time, &idx, ans);
    for (int i = 0; i < n; ++i) {
        freeAdjNode(graph[i]);
    }
    free(graph);
    return ans;
}




int main() {
    int **redEdges;
    redEdges = (int **) calloc(2, sizeof(int *));
    redEdges[0] = (int *) calloc(2, sizeof(int));
    redEdges[0][0] = 0;
    redEdges[0][1] = 1;
    redEdges[1] = (int *) calloc(2, sizeof(int));
    redEdges[1][0] = 1;
    redEdges[1][1] = 2;
    int **blueEdges = NULL;

    int size;
    shortestAlternatingPaths(3, redEdges, 2, NULL, blueEdges, 0, NULL, &size);

    printf("returnsize is %d", size);
}